package leetcode.binaryTree;

import datastructure.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
 * <p>
 * 给定两个整数数组，preorder和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
 * <p>
 * 如果存在多个答案，您可以返回其中 任何 一个。
 * <p>
 * 草稿(旧) 9
 * @Author Ammar
 * @Create 2023/4/1 01:13
 */
public class _889_根据前序和后序遍历构造二叉树 {
    static Map<Integer, Integer> preorderMap = new HashMap<>();
    static Map<Integer, Integer> postorderMap = new HashMap<>();
    public static TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < preorder.length; i++) {
            preorderMap.put(preorder[i], i);
            postorderMap.put(postorder[i], i);
        }
        return constructFromPrePost(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
    }
    /**
     * 1 2 4 5 3 6 7
     * 4 5 2 6 7 3 1
     *
     * @param prs
     * @param pre
     * @param pos
     * @param poe
     * @return
     */
    public static TreeNode constructFromPrePost(int[] preorder, int[] postorder, int prs, int pre, int pos, int poe) {
        if (pre < prs || poe < pos) return null;
        // 获取根节点
        int root = preorder[prs];
        TreeNode treeNode = new TreeNode(root, null);
        // 只有一个节点
        if (pre == prs) return treeNode;
        // 获取左子树的根节点
        int leftRoot = preorder[prs + 1];
        // 获取右子树的根节点
        int rightRoot = postorder[poe - 1];
        // 左子树的前序遍历下标范围
        int leftPreStart = prs + 1;
        Integer preRightNodeIndex = preorderMap.get(rightRoot);
        int leftPreEnd = preRightNodeIndex - 1;
        // 左子树的后序遍历下标范围
        int leftPostStart = pos;
        int leftPostEnd = postorderMap.get(leftRoot);
        // 构建二叉树
        treeNode.left = constructFromPrePost(preorder, postorder, leftPreStart, leftPreEnd, leftPostStart, leftPostEnd);
        // 右子树的前序遍历下标范围
        int rightPreStart = preRightNodeIndex;
        int rightPreEnd = pre;
        // 右子树的后序遍历下标范围
        int rightPostStart = leftPostEnd + 1;
        int rightPostEnd = poe - 1;
        treeNode.right = constructFromPrePost(preorder, postorder, rightPreStart, rightPreEnd, rightPostStart, rightPostEnd);
        return treeNode;
    }

    // 测试一下上面的方法
    public static void main(String[] args) {
        int[] preorder = new int[]{1, 2, 4, 5, 3, 6, 7};
        int[] postorder = new int[]{4, 5, 2, 6, 7, 3, 1};
        TreeNode treeNode = constructFromPrePost(preorder, postorder);
        // 已知二叉树的根节点是treeNode，输出二叉树的全部元素
        System.out.println(treeNode);
    }

}
